<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8" />
  <meta name="viewport" content="width=device-width, initial-scale=1.0" />
  <title>Graph</title>
</head>

<body>
  <script>
    class Queue {
      constructor() {
        this.arr = [];
      }
      // 入栈
      enqueue(ele) {
        this.arr.push(ele);
      }
      // 出栈
      dequeue() {
        return this.arr.shift();
      }
      // 返回队列第一个元素
      front() {
        return this.arr[0];
      }
      isEmpty() {
        return this.arr.length === 0;
      }
      size() {
        return this.arr.length;
      }
      toString() {
        var str = "";
        for (var i = 0; i < this.arr.length; i++) {
          str += this.arr[i] + " ";
        }
        return str;
      }
    }
    class Dictionary {
      constructor() {
        this.items = {};
      }
      set(key, value) {
        this.items[key] = value;
      }
      has(key) {
        return this.items.hasOwnProperty(key);
      }
      remove(key) {
        if (!this.has(key)) return false;
        delete this.items[key];
        return true;
      }
      get(key) {
        return this.has(key) ? this.items[key] : undefined;
      }
      keys() {
        return Object.keys(this.items);
      }
      values() {
        return Object.values(this.items);
      }
      size() {
        return this.keys().length;
      }
      clear() {
        this.items = {};
      }
    }
    class Graph {
      constructor() {
        // 顶点
        this.vertexes = [];
        // 边
        this.edges = new Dictionary();
      }
      // 添加顶点
      addVertex(v) {
        this.vertexes.push(v);
        this.edges.set(v, []);
      }
      // 添加边
      addEdge(v1, v2) {
        // 有向 this.edges.get(v1).push(v2);
        // 无向
        this.edges.get(v1).push(v2);
        this.edges.get(v2).push(v1);
      }
      toString() {
        let str = "";
        for (let i = 0; i < this.vertexes.length; i++) {
          str += this.vertexes[i] + "-> ";
          let edgesArr = this.edges.get(this.vertexes[i]);
          for (let j = 0; j < edgesArr.length; j++) {
            str += edgesArr[j] + " ";
          }
          str += "\n";
        }
        return str;
      }
      // 遍历 - 广度优先搜索BFS 
      bfs(initV, handler) {
        let status = Graph.initializeStatus(this.vertexes),
          queue = new Queue();
        // 进入队列
        queue.enqueue(initV);
        while (!queue.isEmpty()) {
          // 从队列中取出第一个顶点
          let v = queue.dequeue(),
            // 获取顶点相连的另位顶点
            vlist = this.edges.get(v);

          // 将v颜色设置为访问过状态
          status[v] = "1";
          // 遍历所有顶点 并加入队列
          for (let i = 0; i < vlist.length; i++) {
            let e = vlist[i];
            if (status[e] === "0") {
              status[e] = "1";
              queue.enqueue(e);
            }
          }
          // v已经访问完全
          handler(v);
          status[v] = "2";
        }
      }
      // 遍历 - 深度优先搜索DFS
      dfs(initV, handler) {
        let status = Graph.initializeStatus(this.vertexes)
        Graph.dfsVisit(initV, this.edges, status, handler)
      }
      // 未访问0 访问1 完全访问2
      // 初始化状态
      static initializeStatus(vertexes) {
        let status = [];
        for (let i = 0; i < vertexes.length; i++) {
          status[vertexes[i]] = "0";
        }
        return status;
      }
      static dfsVisit(v, edges, status, handler) {
        // 状态设置为经过状态
        status[v] = '1';
        // 处理v顶点
        handler(v)
        // 访问v相邻的顶点
        let vlist = edges.get(v);

        for (let i = 0; i < vlist.length; i++) {
          let e = vlist[i]
          if (status[e] == '0') {
            Graph.dfsVisit(e, edges, status, handler)
          }
        }
        // 将v状态设置为完全访问
        status[v] = '2';

      }
    }
    let g = new Graph();
    let arr = ["A", "B", "C", "D", "E", "F", "G", "H", "I"];
    for (let i = 0; i < arr.length; i++) {
      g.addVertex(arr[i]);
    }
    g.addEdge("A", "B");
    g.addEdge("A", "C");
    g.addEdge("A", "D");
    g.addEdge("C", "D");
    g.addEdge("C", "G");
    g.addEdge("D", "G");
    g.addEdge("D", "H");
    g.addEdge("B", "E");
    g.addEdge("B", "F");
    g.addEdge("E", "I");
    console.log(g.toString());
    // g.bfs("A", (v) => {
    //   console.log(v);
    // });
    g.dfs("A", (v) => {
      console.log(v);
    })
  </script>
</body>

</html>